package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;

import java.util.*;

public class Subsets2 {

    /**
     * dfs
     *
     * @param nums 1 <= nums.length <= 10
     *             -10 <= nums[i] <= 10
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        dfs(0, new LinkedList<>(), nums, res);
        return res;
    }

    private void dfs(int index, LinkedList<Integer> path, int[] nums, List<List<Integer>> res){
        res.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; ++i){
            // 如果当前元素已被标记或者和之前一样，就不放入子集中
            if (nums[i] == Integer.MIN_VALUE || (i > 0 && nums[i] == nums[i - 1])){
                continue;
            }
            path.addLast(nums[i]);
            nums[i] = Integer.MIN_VALUE;
            dfs(i + 1, path, nums, res);
            nums[i] = path.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] nums = {-1,1,2};
        List<List<Integer>> lists = new Subsets2().subsetsWithDup(nums);
        System.out.println(lists);
        List<List<Integer>> parse = ArrayUtils.parse("[[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]");
        System.out.println(ArrayUtils.allMatch(lists, parse));
    }

}
